In this paper, we propose an approach to test pattern generation for Speed-Independent (SI) asynchronous control circuits. Test patterns are generated based on a specified sequence, which is derived from the specification of a target circuit in the form of a Signal Transition Graph (STG). Since the sequence represents the behavior of a circuit only with stable states, the state space of the circuit can be represented as reduced one. A product machine, which consists of a fault-free circuit and a faulty circuit, is constructed and then the specified sequence is applied sequentially to the product machine. A fault is detected when the product machine produces inconsistency, i.e., output values of a fault-free circuit and a faulty circuit are different, and the sequentially applied part of the sequence becomes a test pattern to detect the fault. We also propose a test generation method using an undetectable fault identification as well as the specified sequence. Since the reduced state space is a subset of that of a gate level implementation, test patterns based on a specification cannot detect some faults. The proposed method identifies those faults with a circuit topology in advance. BDD is used to implement the proposed methods efficiently, since the proposed methods have a lot of state sets and set operations. Experimental results show that the test generation using a specification achieves high fault coverage over single stuck-at fault model for several synthesized SI circuits. The proposed test generation using a circuit topology as well as a specification decreases execution time for test generation with negligible cost retaining high fault coverage.

There have been few studies on formal approaches to the specification and realization of asynchronous sequential circuits. For synchronous sequential circuits, an algebraic method is proposed as one of such approaches, but it cannot be applied to asynchronous ones directly. This paper describes an algebraic method of specifying the abstract behavior of asynchronous sequential circuits. We select an daisy chain arbiter as an example of them. In the arbiter, state transitions are caused by input changes, and all the modules do not always make state transitions simultaneously. These are main obstacles to specify it in the same way as sychronous sequential circuits. In order to remove them, we modify the meaning of input in specifications and introduce pseudo state transitions so that we can regard all the modules as if they make state transitions simultaneously. This method can be applied to most of the other asynchronous sequential circuits.